// 算法思想
// 根据问题得到对应分解的子问题，首先如果假设要偷n家求获得利润的最大值fn，那么可以得到其子问题为偷k家求获得利润的最大值fk，其中k<=n
// 然后看子问题能否被通过使用其他子问题进行解决，上述中fk可以由f(k-1)和f(k-2)进行解决
// 因为当我们要求fk的时候，可以把这个问题理解为要么就是不要偷第k家，那么对应的结果就是f(k-1)（因为连续偷盗会触发警报）
// 或则就是不偷第f(k-1)家，进而去偷f(k-2)家，那么fk的结果应为f(k-2)+num[k]也就是偷f(k-2)家的最大利润加上第k家能偷到的钱
// 因此我们得到了最优子结构就是fk = Max(f(k-1),f(k-2)+nums[k])
// 然后再看最小子问题的结果
// 当房子为0时，没有东西可偷那么就是0元
// 当房子数为1时，那只能偷这一家，那么房子数就是盖房子能获得价值
// 最后根据上述最优子结构，然后根据自底向上的规律，得到n所房子内能获得的最大价值



/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {

  if (nums.length == 0) return 0
  let fi = 0
  if (nums.length == 1) return nums[0]
  let fj = nums[0]
  let fk = 0
  for (let i = 1; i < nums.length; i++) {
    fk = Math.max(fj, fi + nums[i])
    fi = fj
    fj = fk
  }
  return fk;
};
rob([2, 7, 9, 3, 1])